package com.demo.study.algorithm.cases;

import java.util.LinkedList;

/**
 * 汉诺塔
 *
 * @author Baymax
 * @since 2024-08-13
 */
public class C01_HanoiTower {
    private static LinkedList<Integer> a;

    private static LinkedList<Integer> b;

    private static LinkedList<Integer> c;

    public static void main(String[] args) {
        int num = 3;
        init(num);
        print();
        move(num, a, b, c);
    }

    /**
     * 移动过程
     * <p>
     * 有两个圆盘时:
     * <li>圆盘2, a -> b </li>
     * <li>圆盘1, a -> c </li>
     * <li>圆盘2, b -> c </li>
     * <p>
     * 有三个圆盘时:
     * <li>圆盘12, a -> b </li>
     * <li>圆盘 3, a -> c </li>
     * <li>圆盘12, b -> c </li>
     *
     * @param n 圆盘位置
     * @param a A柱
     * @param b B柱
     * @param c C柱
     */
    public static void move(int n, LinkedList<Integer> a, LinkedList<Integer> b, LinkedList<Integer> c) {
        if (n == 0) {
            return;
        }
        move(n - 1, a, c, b); // a 借助c 移动到b
        c.addLast(a.removeLast()); // 中间：a 直接 移动到c
        print();
        move(n - 1, b, a, c); // b 借助a 移动到a
    }

    private static void init(int nums) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = nums; i > 0; i--) {
            list.addLast(i);
        }
        a = list;
        b = new LinkedList<>();
        c = new LinkedList<>();
    }

    private static void print() {
        System.out.println("--------------");
        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
    }
}
